/*
 * @lc app=leetcode.cn id=5 lang=golang
 *
 * [5] 最长回文子串
 */

// @lc code=start
// func preProcess(s string) string {
// 	n := len(s)
// 	if n == 0 {
// 		return "^$"
// 	}
// 	ret := "^"
// 	for i := 0; i < n; i++ {
// 		ret += "#" + string(s[i])
// 	}
// 	ret += "#$"
// 	return ret

// }

// // 马拉车算法
// func longestPalindrome(s string) string {
// 	T := preProcess(s)
// 	n := len(T)
// 	P := [9000]int{}
// 	C := 0
// 	R := 0
// 	for i := 1; i < n-1; i++ {
// 		i_mirror := 2*C - i
// 		if R > i {
// 			P[i] = minInt(R-i, P[i_mirror]) // 防止超出 R
// 		} else {
// 			P[i] = 0 // 等于 R 的情况
// 		}

// 		// 碰到之前讲的三种情况时候，需要利用中心扩展法
// 		for T[i+1+P[i]] == T[i-1-P[i]] {
// 			P[i]++
// 		}

// 		// 判断是否需要更新 R
// 		if i+P[i] > R {
// 			C = i
// 			R = i + P[i]
// 		}

// 	}

// 	// 找出 P 的最大值
// 	maxLen := 0
// 	centerIndex := 0
// 	for i := 1; i < n-1; i++ {
// 		if P[i] > maxLen {
// 			maxLen = P[i]
// 			centerIndex = i
// 		}
// 	}
// 	start := (centerIndex - maxLen) / 2 //最开始讲的求原字符串下标
// 	return s[start : start+maxLen]
// }

// func minInt(x, y int) int {
// 	if x < y {
// 		return x
// 	}
// 	return y
// }

//DP解法
func  longestPalindrome(s string) string {
len := len(s)
if len <= 1 {
	return s
}
temp := 1
longestPalindromeStr := s[0:1]
dp := make([][]bool, len)
for i:=0;i<len;i++{
	dp[i] = make([]bool,len)
}

// abcdedcba
//   l   r
// 如果 dp[l, r] = true 那么 dp[l + 1, r - 1] 也一定为 true
// 关键在这里：[l + 1, r - 1] 一定至少有 2 个元素才有判断的必要
// 因为如果 [l + 1, r - 1] 只有一个元素，不用判断，一定是回文串
// 如果 [l + 1, r - 1] 表示的区间为空，不用判断，也一定是回文串
// [l + 1, r - 1] 一定至少有 2 个元素 等价于 l + 1 < r - 1，即 r - l >  2

// 写代码的时候这样写：如果 [l + 1, r - 1]  的元素小于等于 1 个，即 r - l <=  2 ，就不用做判断了

// 因为只有 1 个字符的情况在最开始做了判断
// 左边界一定要比右边界小，因此右边界从 1 开始
for  r := 1; r < len; r++ {
	for  l := 0; l < r; l++ {
		// 区间应该慢慢放大
		// 状态转移方程：如果头尾字符相等并且中间也是回文
		// 在头尾字符相等的前提下，如果收缩以后不构成区间（最多只有 1 个元素），直接返回 True 即可
		// 否则要继续看收缩以后的区间的回文性
		// 重点理解 or 的短路性质在这里的作用
		if s[l] == s[r] && (r - l <= 2 || dp[l + 1][r - 1]) {
			dp[l][r] = true
			if r - l + 1 > temp {
				temp = r - l + 1
				longestPalindromeStr = s[l : r + 1]
			}
		}
	}
}
return longestPalindromeStr
}
// @lc code=end

